{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "leetcode22.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "VjKPjutxE_oH"
      },
      "source": [
        "class Solution(object):\n",
        "    def generateParenthesis(self, n):\n",
        "        \"\"\"\n",
        "        :type n: int\n",
        "        :rtype: List[str]\n",
        "        \"\"\"\n",
        "        ret = []\n",
        "        self.backtrack(ret, \"\", 0, 0, n)\n",
        "        return ret \n",
        "    \n",
        "    def backtrack(self, ret, cur_str, left_num, right_num, n):\n",
        "        \n",
        "        # base case \n",
        "        if (len(cur_str) == 2 * n):\n",
        "            ret.append(cur_str)\n",
        "            return ret \n",
        "        \n",
        "        if (left_num < n):\n",
        "            self.backtrack(ret, cur_str + \"(\", left_num + 1, right_num, n)\n",
        "            \n",
        "        if (right_num < left_num):\n",
        "            self.backtrack(ret, cur_str + \")\", left_num, right_num + 1, n)"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rzKHG8RBFFKE",
        "outputId": "bd5dfa98-f43f-4480-8833-ac861fb98a79",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        }
      },
      "source": [
        "  s = Solution()\n",
        "  print(s.generateParenthesis(3))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "['((()))', '(()())', '(())()', '()(())', '()()()']\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}